\documentclass{article}
\usepackage{silaboUNSA}

\year{2009-A}

\course{Análisis y Diseño de Algoritmos}
\courseCode{0202218}
\credits{3 (Tres)}
\semester{V}
\prerequisites{0202219}
\weekTime{4}
\T{2}
\TP{2}
\P{0}
\S{0}

%descomentar el día adecuado e indicar el salón
%\monday{203}
\tuesday{18:00-20:00}{201}
\wednesday{18:00-20:00}{201}
%\thursday{15:30-17:00}{201}
%\friday{10:15-11:45}{201}
%\saturday{}

\teacher{Alfredo Paz Valderrama}
\teacherDegree{Bachiller}
\profession{Ingeniero de Sistemas}

\begin{document}

\maketitle

\begin{data} 
   \makeData
\end{data}

\begin{motivation}
``Los Algoritmos son fundamentales para la ciencia de computación y la ingeniería del software. El rendimiento, en el mundo real, de cualquier sistema de software depende sólo de dos cosas: (1) El algoritmo que se usa y (2) la conveniencia y eficiencia de varias capas de implementación. Los buenos diseños de algoritmos son por tanto, cruciales en el desempeño de todo sistema de software. Por otra parte, el estudio de algoritmos provee técnicas de solución independientes del lenguaje de programación, paradigma de programación, hardware y cualquier otro aspecto de implementación.''
\end{motivation}

\begin{objective}
   Aprender las técnicas de diseño, así como el analizar la eficiencia de distintos algoritmos.
\end{objective}

\begin{temas}

   \unit{Análisis de Algoritmos}{
      \obj Estudiar la importancia de los algoritmos en la solución de problemas computacionales.
      \obj Usar la rigurosidad matemática y técnicas de ingeniería para el estudio del desempeño de los algoritmos.
      \obj Analizar el desempeño de algoritmos tanto en tiempo como espacio.
      \obj Identificar los mejores, peores y escenarios para el desempeño de un algoritmo, así  como el escenerio esperado.
      \obj Revisar distintas técnicas para la solución de ecuaciones de recurrencia.
      \obj Comparar el desempeño teórico con el desempeño real.
   }{
      \tema Importancia de los Algoritmos en la solución de problemas.
      \tema Cálculo del tiempo y espacio en algoritmos.   
      \tema Análisis asintótico y Notación asintótica: Comparación de la tendencia de funciones, $O$, $o$, $\Theta$, $\Omega$, $\varpi$; definición formal y demostración de sus propiedades.
      \tema Análisis del mejor, peor y caso promedio: insertion sort, merge sort.
      \tema Técnicas de solución de recurrencias: árbol de recursión, inducción, funciones generatrices, el teorema maestro.
      \tema Incidencia de factores externos y la implementación de algoritmos

      \begin{lecturas}
         \obligatoria{Cormen01, FerVid99}
         \sugerida{GrahmKnuthPatashnik95, BaezaYates95, Knuth98, aho1983, Wilf94}
      \end{lecturas}
   }
   {20}
   {12, 13, 19, 20, 26, 27 enero; 02, 03, 09, 10 febrero}
   {31}
   
   \unit{Técnicas de Diseño de Algoritmos}{
      \obj Observar el facilismo de los algortimos de fuerza bruta.
      \obj Estudiar las principales técnicas de diseño de algoritmos.
      \obj Implementar algoritmos estudiados.
   }{
      \tema Algoritmos de fuerza bruta
      \tema Divide y Vencerás: Strassen, Fibonacci, Polynomial Multiplication, Quick Sort.  
      \tema Algoritmos avaros: Minimum Spanning Trees.
      \tema Programación Dinámica: Longest Common Subsequence.
      \begin{lecturas}
         \obligatoria{Cormen01}
         \sugerida{aho1983, Knuth98}
      \end{lecturas}

   }
   {24}
   {16, 17, 23, 24 febrero; 02, 03, 09, 10, 16, 17, 23, 24 marzo}
   {69}
   
   
   \unit{Algoritmos fundamentales}{
      \obj Usar patrones de búsqueda para analizar subcadenas.
      \obj Usar aproximaciones numéricas para resolver problemas matemáticos, tales como encontrar las raíz de un polinomio.
      \obj Discutir los distintos factores que influyen en la eficiencia de los algoritmos implementados.
      \obj Estudiar a los grafos como estructura de representación de problemas reales.
   }{
      \tema Backtracking.
      \tema Branch and bound.
      \tema Heurísticas.
      \tema Algoritmos de la ruta más corta: Dijkstra, Floyd, Bellman-Ford, Linear Programming, Floyd-Warshall, Johnson. 
      \tema Algoritmos de búsqueda para patrones de texto.
      \tema Algoritmos de aproximación numérica.
      \begin{lecturas}
         \obligatoria{Cormen01}
         \sugerida{Knuth98, aho1983}
      \end{lecturas}

   }
   {8}
   {30, 31 marzo; 06, 07 abril}
   {81}
   
   
   \unit{Las Clases de Complejidad P y NP}{
      \obj Definir las clases P y NP.
      \obj Entender el significado de NP-completidud.   
      \obj Probar que un problema es NP-completo reduciéndolo a un problema NP conocido.
   }{
      \tema Definición de las clases P y NP
      \tema NP completitud (Teorema de Cook).
      \tema Problemas NP-completos estándares.
      \begin{lecturas}
         \obligatoria{Cormen01}
         \sugerida{Wilf94}
      \end{lecturas}

   }
   {12}
   {13, 14, 20, 21, 27, 28 Abril}
   {100}
   
   
\end{temas}

\begin{actividades}
   \act Tareas
   \act Proyecto del curso
   \act Intervenciones en clase
   \act Controles escritos
\end{actividades}

\begin{recursos}
   \rec Página Web y Lista de Interes \\
   \url{http://groups.google.com/group/episunsa-ada}
   \rec Material del MIT\\
   \url{http://ocw.mit.edu/OcwWeb/Electrical-Engineering-and-Computer-Science/6-046JFall-2005/ LectureNotes/index.htm}
\end{recursos}

\begin{bibliografia}
\end{bibliografia}

\begin{metodologia}
El curso buscará propiciar el construccionismo y social-construccionismo.
\end{metodologia}


\begin{evaluacion}
La nota final (NF) se obtiene de la siguiente manera
\begin{description}
\item[NE] Nota de Examenes 45 \%, esta nota se divide en
   \begin{itemize}
   \item Examen Parcial 40 \%
   \item Examen Final 60 \%
   \end{itemize}
\item[NT] Nota de Trabajos e Intervencion en clase 25 \%
\item[NP] Nota del proyecto de curso 30\%
\end{description}

\begin{math}
NF = 0,45 * NE + 0,25 * NT + 0,3 * NP 
\end{math}

\end{evaluacion}

\date{Enero del 2010}


\end{document}
